package sort;


/**
 * @Author: LDeng
 * @Date: 2021-03-29 9:29
 */
public class CountingSort extends Sort<Integer> {

    @Override
    protected void sort() {
        //找出最大值，最小值
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }

        int[] counts = new int[max - min + 1];
        //统计每个整数出现的次数，不累加
        for (int i = 0; i < array.length; i++) {
            counts[array[i] - min]++;
        }
        //累加次数， 索引-1的值 加上自己的值的，覆盖自己的值
        //得到累加次数的数组
        for (int i = 1; i < counts.length; i++) {
            counts[i] = counts[i - 1] + counts[i];
        }
        //从后往前遍历array元素， 将它放到有序数组中的合适位置
        int[] newArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            //将遍历到的数字放到新数组的counts[array[i]-min]-1 索引位置
            //将counts[array[i]-min] 减掉一个
            counts[array[i] - min] = counts[array[i] - min] - 1;
            newArray[counts[array[i] - min]] = array[i];

        }
        //将有序数组覆盖回array
        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }


    }


    protected void sort0() {
        //找出最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        //开辟内存空间， 存储每个整数出现的次数
        int[] counts = new int[max + 1];
        //统计每个整数出现的次数
        for (int i = 0; i < array.length; i++) {
            counts[array[i]]++;//counts数组中arry[i]索引记录的是整数出现过的次数
        }

        //根据整数出现次数，堆整数进行排序
        int index = 0;
        for (int i = 0; i < counts.length; i++) {
            while (counts[i] > 0) {
                array[index] = i;
                index++;
                counts[i]--;
            }
        }
    }

    private static class Person {
        int age;
        String name;

        Person(int age, String name) {
            this.age = age;
            this.name = name;
        }

        @Override
        public String toString() {
            return "Person [age=" + age
                    + ", name=" + name + "]";
        }
    }

    public static void main(String[] args) {
        Person[] persons = new Person[]{
                new Person(20, "A"),
                new Person(-13, "B"),
                new Person(17, "C"),
                new Person(12, "D"),
                new Person(-13, "E"),
                new Person(20, "F")
        };

        sortPerson(persons);
        for (Person person : persons) {
            System.out.println(person);
        }
    }

    public static void sortPerson(Person[] persons) {
        //找出最大值，最小值
        int max = persons[0].age;
        int min = persons[0].age;
        for (int i = 1; i < persons.length; i++) {
            if (persons[i].age > max) {
                max = persons[i].age;
            }
            if (persons[i].age < min) {
                min = persons[i].age;
            }
        }

        int[] counts = new int[max - min + 1];
        //统计每个整数出现的次数，不累加
        for (int i = 0; i < persons.length; i++) {
            counts[persons[i].age - min]++;
        }
        //累加次数， 索引-1的值 加上自己的值的，覆盖自己的值
        //得到累加次数的数组
        for (int i = 1; i < counts.length; i++) {
            counts[i] = counts[i - 1] + counts[i];
        }
        //从后往前遍历array元素， 将它放到有序数组中的合适位置
        Person[] newArray = new Person[persons.length];
        for (int i = persons.length - 1; i >= 0; i--) {
            //将遍历到的数字放到新数组的counts[array[i]-min]-1 索引位置
            //将counts[array[i]-min] 减掉一个
            counts[persons[i].age - min] = counts[persons[i].age - min] - 1;
            newArray[counts[persons[i].age - min]] = persons[i];

        }
        //将有序数组覆盖回array
        for (int i = 0; i < newArray.length; i++) {
            persons[i] = newArray[i];
        }
    }

}
